#ifndef GRAPH_TYPE_HPP
#define GRAPH_TYPE_HPP
#include <chrono>
#include <queue>
#include <unordered_map>
#include <utility>
#include <vector>
//=============== DEFINE TYPE ===============
struct Vertex {
  bool visited = false;
  int node{0};
  time_t start{0};
  time_t end{0};
  int pnum{0};
  int id{0};
  int topo_id{0};        // topological order
  bool in_tree = false;  // 标记是否出现在树中
};

using EdgeList = std::vector<int>;  // edge list represented by vertex id list
using VertexList = std::vector<Vertex>;  // vertices list (store real vertex
                                         // property) indexing by id
struct In_OutList {
  EdgeList inList;
  EdgeList outList;
};

class Hasher {
 public:
  size_t operator()(const std::pair<int, time_t>& p) const {
    size_t h1 = (uint64_t) p.first << 32;
    size_t h2 = p.second;
    return h1 | h2;
  }
};

class Equaler {
 public:
  bool operator()(const std::pair<int, time_t>& a,
                  const std::pair<int, time_t>& b) const {
    // 仅比较开始时间和关联的地点，因为同一个地点的划分出的clique的时间区间相互不覆盖
    return a.first == b.first && a.second == b.second;
  }
};
using GRA = std::vector<In_OutList>;
using Cfunc = std::unordered_map<std::pair<int, time_t>, int, Hasher, Equaler>;

class Graph {
 private:
  GRA graph;
  VertexList vl;
  int vsize;
  Cfunc f;

 public:
  Graph();
  Graph(int);
  Graph(const Graph&);
  Graph(GRA&, VertexList&);
  ~Graph();

  void addVRoot();
  void addVertex(Vertex);
  void addVertex(int node, time_t start, time_t end);
  void addVertex(int node, time_t start, time_t end, int num);
  void addEdge(int, int);
  void addEdge(std::pair<int, time_t>, std::pair<int, time_t>);
  std::vector<int> topological_sort();
  int num_vertices();
  int num_edges();
  VertexList& vertices();
  EdgeList& out_edges(int);
  EdgeList& in_edges(int);
  int out_degree(int);
  int in_degree(int);
  int cnum(std::pair<int, time_t>);
  std::vector<int> getRoots();
  bool hasEdge(int, int);
  Graph& operator=(const Graph&);
  Graph& operator=(Graph&&);
  Vertex& operator[](const int);
};
Graph::Graph() {
  graph = GRA();
  vl = VertexList();
}

Graph::Graph(int size) {
  vsize = size;
  vl = VertexList(size);
  graph = GRA(size, In_OutList());
}

Graph::Graph(const Graph& other) {
  if (this != &other) {
    graph = other.graph;
    vl = other.vl;
    f = other.f;
    vsize = other.vsize;
  }
}

Graph::Graph(GRA& g, VertexList& vlist) {
  vsize = vlist.size();
  graph = g;
  vl = vlist;
}

Graph::~Graph() {}

void Graph::addVRoot() {
  int vid = vl.size();
  graph.push_back(In_OutList());
  vl.push_back(Vertex());
  vsize = vl.size();

  Vertex v;
  v.node = -1;
  v.visited = false;
  vl[vid] = v;
  vl[vid].id = vid;
  f[std::make_pair(v.node, v.start)] = vid;
  EdgeList il = EdgeList();
  EdgeList ol = EdgeList();
  In_OutList oil = In_OutList();
  oil.inList = il;
  oil.outList = ol;
  graph[vid] = oil;
}

void Graph::addVertex(Vertex v) {
  if (f.find(std::make_pair(v.node, v.start)) == f.end()) {
    int vid = vl.size();
    graph.push_back(In_OutList());
    vl.push_back(Vertex());
    v.id = vid;
    vl[vid] = v;
    f[std::make_pair(v.node, v.start)] = vid;
    vsize = vl.size();

    EdgeList il = EdgeList();
    EdgeList ol = EdgeList();
    In_OutList oil = In_OutList();
    oil.inList = il;
    oil.outList = ol;
    graph[vid] = oil;
  }
}

void Graph::addVertex(int node, time_t start, time_t end) {
  if (f.find(std::make_pair(node, start)) == f.end()) {
    int vid = vl.size();
    graph.push_back(In_OutList());
    vl.push_back(Vertex());
    f[std::make_pair(node, start)] = vid;
    vsize = vl.size();

    Vertex v;
    v.visited = false;
    v.node = node;
    v.start = start;
    v.end = end;
    v.id = vid;
    vl[vid] = v;

    EdgeList il = EdgeList();
    EdgeList ol = EdgeList();
    In_OutList oil = In_OutList();
    oil.inList = il;
    oil.outList = ol;
    graph[vid] = oil;
  }
}

void Graph::addVertex(int node, time_t start, time_t end, int num) {
  if (f.find(std::make_pair(node, start)) == f.end()) {
    int vid = vl.size();
    graph.push_back(In_OutList());
    vl.push_back(Vertex());
    f[std::make_pair(node, start)] = vid;
    vsize = vl.size();

    Vertex v;
    v.visited = false;
    v.node = node;
    v.start = start;
    v.end = end;
    v.id = vid;
    v.pnum = num;
    vl[vid] = v;

    EdgeList il = EdgeList();
    EdgeList ol = EdgeList();
    In_OutList oil = In_OutList();
    oil.inList = il;
    oil.outList = ol;
    graph[vid] = oil;
  }
}

void Graph::addEdge(int sid, int tid) {
  // update edge list
  graph[tid].inList.push_back(sid);
  graph[sid].outList.push_back(tid);
}

void Graph::addEdge(std::pair<int, time_t> a, std::pair<int, time_t> b) {
  int sid = cnum(a);
  int tid = cnum(b);
  graph[tid].inList.push_back(sid);
  graph[sid].outList.push_back(tid);
}

std::vector<int> Graph::topological_sort() {
  std::vector<int> order;
  std::queue<int> q;
  std::vector<int> ind(vsize, 0);
  for (int i = 0; i < vsize; i++) {
    ind[i] = this->in_degree(i);
    if (ind[i] == 0)
      q.push(i);
  }

  while (q.size() > 0) {
    int v = q.front();
    q.pop();
    order.push_back(v);
    for (int j : this->out_edges(v)) {
      ind[j]--;
      if (ind[j] == 0)
        q.push(j);
    }
  }
  return order;
}

int Graph::num_vertices() { return vl.size(); }

int Graph::num_edges() {
  EdgeList el;
  GRA::iterator git;
  int num = 0;
  for (git = graph.begin(); git != graph.end(); git++) {
    el = git->outList;
    num += el.size();
  }
  return num;
}

// return out edges of specified vertex
EdgeList& Graph::out_edges(int src) { return graph[src].outList; }

// return in edges of specified vertex
EdgeList& Graph::in_edges(int trg) { return graph[trg].inList; }

int Graph::out_degree(int src) { return graph[src].outList.size(); }

int Graph::in_degree(int trg) { return graph[trg].inList.size(); }

int Graph::cnum(std::pair<int, time_t> p) { return f[p]; }

// get roots of graph (root is zero in_degree vertex)
std::vector<int> Graph::getRoots() {
  std::vector<int> roots;
  GRA::iterator git;
  int i = 0;
  for (git = graph.begin(), i = 0; git != graph.end(); git++, i++) {
    if (git->inList.size() == 0)
      roots.push_back(i);
  }

  return roots;
}

// check whether the edge from src to trg is in the graph
bool Graph::hasEdge(int src, int trg) {
  EdgeList el = graph[src].outList;
  EdgeList::iterator ei;
  for (ei = el.begin(); ei != el.end(); ei++)
    if ((*ei) == trg)
      return true;
  return false;
}

// return vertex list of graph
VertexList& Graph::vertices() { return vl; }

Graph& Graph::operator=(const Graph& g) {
  if (this != &g) {
    graph = g.graph;
    vl = g.vl;
    vsize = g.vsize;
    f = g.f;
  }
  return *this;
}

Graph& Graph::operator=(Graph&& other) {
  if (this != &other) {
    graph = std::move(other.graph);

    // 移动 vl
    vl = std::move(other.vl);

    // 移动 vsize
    vsize = other.vsize;

    // 重置源对象的成员变量
    other.vsize = 0;
  }
  return *this;
}

// get a specified vertex property
Vertex& Graph::operator[](const int vid) { return vl[vid]; }

#endif